/*Hefei 2008-2009 Triangles to count the numbers of red-blue triangles and green-blue triangles. ÌÝÐÎÆÊ·Öo(n^3) */ #include #include #include #include #include using namespace std; #define maxn 110 struct Nodes{ int x,y; }r[maxn],g[maxn],b[maxn]; int nr,ng,nb; int below[maxn][maxn][2]; int hav[maxn][2]; bool cmp(Nodes aa,Nodes bb) { if(aa.x!=bb.x)return aa.xb[i].x&&r[k].xr[k].y)below[i][j][0]++; } } for(k=1;k<=ng;k++){ if(g[k].x>b[i].x&&g[k].xg[k].y)below[i][j][1]++; } } } } ans1=ans2=0; for(i=1;i<=nb;i++){ for(j=i+1;j<=nb;j++){ for(k=j+1;k<=nb;k++){ cnt1=cnt2=0; tmp=(b[k].y-b[i].y)*(b[j].x-b[i].x)*1.0/(b[k].x-b[i].x)+b[i].y; if(tmpcnt2)ans1++; }else{ cnt1=-below[i][j][0]-below[j][k][0]+below[i][k][0]-hav[j][0]; cnt2=-below[i][j][1]-below[j][k][1]+below[i][k][1]-hav[j][1]; if(cnt1cnt2)ans1++; } } } } cas++; printf("Case %d: %d %d\n",cas,ans1,ans2); } return 0; }